/*
题目：从上到下打印二叉树Ⅲ
请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。
https://leetcode.cn/problems/cong-shang-dao-xia-da-yin-er-cha-shu-iii-lcof/
 */
public class Offer32Ⅲ {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> list = new ArrayList<> ();
        if (root == null) return list;
        Stack<TreeNode> stackLeft = new Stack<>();  //从左边开始读取的栈
        Stack<TreeNode> stackRight = new Stack<> ();  //从右边开始读取的栈
        stackLeft.push(root);
        while (!stackLeft.isEmpty() || !stackRight.isEmpty()) {
            List<Integer> newLine = new ArrayList<>();
            if (!stackLeft.isEmpty()){
                while (!stackLeft.isEmpty()) {
                    TreeNode cur = stackLeft.pop();
                    newLine.add(cur.val);
                    if (cur.left != null) {
                        stackRight.push(cur.left);
                    }
                    if (cur.right != null) {
                        stackRight.push(cur.right);
                    }
                }
            } else {
                while (!stackRight.isEmpty()) {
                    TreeNode cur = stackRight.pop();
                    newLine.add(cur.val);
                    if (cur.right != null) {
                        stackLeft.push(cur.right);
                    }
                    if (cur.left != null) {
                        stackLeft.push(cur.left);
                    }
                }
            }
            list.add(newLine);
        }

        return list;
    }
}
